#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <ctime>

using namespace std;

void AffichageGraphique(unsigned int n, unsigned int point[][2], unsigned int arbre[][2])       // Cree le fichier Exemple.ps qui affiche
                                                                     // les points et l'arbre de Kruskal.
{
	ofstream output;
	output.open("Kruskal.ps",ios::out);
	output << "%!PS-Adobe-3.0" << endl;
	output << "%%BoundingBox: 0 0 612 792" << endl;
	output << endl;  
	for(unsigned int i=0;i<n;i++)
	{
		output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
		output << "0 setgray" <<endl;
		output << "fill" <<endl;
		output << "stroke"<<endl;
		output << endl;
	}
	
	output << endl;
	for(unsigned int i=0;i<n-1;i++)
	{
		output << point[arbre[i][0]][0] << " " << point[arbre[i][0]][1] 
		<< " moveto" << endl;
		output << point[arbre[i][1]][0] << " " << point[arbre[i][1]][1] 
		<< " lineto" << endl;
		output << "stroke" << endl;
		output << endl;
	}
}


void AffichageGraphiqueComplet(unsigned int n, unsigned int m, unsigned int point[][2], unsigned int edge[][3])
{
	ofstream output;
	output.open("Complet.ps",ios::out);
	output << "%!PS-Adobe-3.0" << endl;
	output << "%%BoundingBox: 0 0 612 792" << endl;
	output << endl;
	for(unsigned int i=0;i<n;i++)
	{
		output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
		output << "0 setgray" <<endl;
		output << "fill" <<endl;
		output << "stroke"<<endl;
		output << endl;
	}
	
	output << endl;
	for(unsigned int i=0;i<m;i++)
	{
		output << point[edge[i][0]][0] << " " << point[edge[i][0]][1] 
				<< " moveto" << endl;
		output << point[edge[i][1]][0] << " " << point[edge[i][1]][1] 
				<< " lineto" << endl;
		output << "stroke" << endl;
		output << endl;
	}
}

void tri(unsigned int m, unsigned int edge[][3])
{
	for(unsigned int i(0); i<m-1; i++)
	{
		for(unsigned int j(i+1); j < m; j++)
		{
			if(edge[i][2] > edge[j][2])
			{
				for(int x(0); x<3; x++)
				{
					unsigned int aux = edge[j][x];
					edge[j][x] = edge[i][x];
					edge[i][x] = aux;
				}
			}
		}
	}
}



void kruskal(unsigned int n, unsigned int m, unsigned int edge[][3], unsigned int arbre[][2])
{
	tri(m, edge);
	unsigned int k(0);
	
	unsigned int* comp = new unsigned int[n];
	
	for(unsigned int i(0); i<n; i++)
	{
		comp[i] = i;
	}
	
	for(unsigned int i(0); i<m; i++)
	{
		if(comp[edge[i][0]] != comp[edge[i][1]])
		{
			unsigned int aux = comp[edge[i][0]];
			arbre[k][0] = edge[i][0];
			arbre[k][1] = edge[i][1];
			
			k++;
			
			for(unsigned int j(0); j<n; j++)
			{
				if(comp[j] == aux)
				{
					comp[j] = comp[edge[i][1]];
				}
			}
		}
	}
	
	delete comp;
}



void pointrandom (unsigned int n, unsigned int point[][2]);
void distances (unsigned int n, unsigned int point[][2], unsigned int edge[][3]);

int main()
{
	srand (time(NULL));

	unsigned int n;             //Le nombre de points.
	std::cout << "Entrer le nombre de points : ";
	std::cin >> n;

	unsigned int m=n*(n-1)/2;   // Le nombre de paires de points.
	
	unsigned int (*point)[2] = new unsigned int [n][2];   // Les coordonnees des points dans le plan.
	unsigned int (*edge)[3] = new unsigned int [m][3];    // Les paires de points et le carre de leur longueur.
	unsigned int (*arbre)[2] = new unsigned int [n-1][2]; // Les aretes de l'arbre de Kruskal.

	pointrandom (n, point);
	distances(n, point, edge);
	
	AffichageGraphiqueComplet(n, m, point, edge);
	
	for(unsigned int i(0); i<m; i++)
	{
		std::cout << "X:" << edge[i][0] << " Y:" << edge[i][1] << " == Dist: " << edge[i][2] << std::endl;
	}
	
	tri(m, edge);
	
	cout << m << std::endl;
	
	for(unsigned int i(0); i<m; i++)
	{
		std::cout << "X:" << edge[i][0] << " Y:" << edge[i][1] << " == Dist: " << edge[i][2] << std::endl;
	}
	
	cout << "0";
	
	kruskal(n, m, edge, arbre);
	
	cout << "1";
	
	AffichageGraphique(n, point, arbre);
	
	cout << "2";

	return 0;
}

void pointrandom (unsigned int n, unsigned int point[][2])
{
	for (unsigned int i(0); i < n; i++)
	{
		point[i][0] = rand()%613;
		point[i][1] = rand()%793;
	}
}

void distances (unsigned int n, unsigned int point[][2], unsigned int edge[][3])
{
	int k(0);
	
	for (unsigned int i(0); i < n; i++)
	{
		for(unsigned int j(i+1); j < n; j++)
		{
			edge[k][0] = i;
			edge[k][1] = j;
			edge[k][2] = (point[j][0] - point[i][0]) * (point[j][0] - point[i][0]) + (point[j][1] - point[i][1]) * (point[j][1] - point[i][1]);
			k++;
		}
	}
}
